# 算法思想：运用kd树，将所有样本点划分至小区域中，每个区域有<2k个实例
# 对于一个测试点，首先找到其对应的区域，找出区域中第k远样本点，然后以此距离去更新最近k个点，直到递归到根节点
# 如果以该距离为半径，测试点为球心的球体与其他区域有交点，则去该区域的点中尝试更新，直到只剩下k个点，且所有涉及区域的点都遍历过

# author@bupt_kt
# date@09/01/2021

import numpy as np
from operator import itemgetter

##读取训练集数据
def input_data():
    data=[]
    file=open(r'Mnist/mnist_train.csv','r')
    for line in file.readlines():
        l=line.strip().split(',')
        data.append([int(num) for num in l[0:]])    ##这里的数据特指数据集中的x
    return data

##进行模型训练
def training(data,k):## k近邻没有显式的学习过程，因此直接测试准确率
    m1=np.mat(data)  ##将数据集转化为矩阵，方便后续运算
    m,n=np.shape(m1) ##获得数据集的行列数
    file = open(r'Mnist/mnist_test.csv', 'r')
    error = 0
    data2 = []
    dist=[]
    for lines in file.readlines(): ##读取测试集
        l = lines.strip().split(',')
        data2.append([int(num) for num in l[0:]])
    m2 = np.mat(data2)
    number,number2 = np.shape(m2)
    area=[]  ##存储每个测试点对应的区域号
    for i in range(number):
        area.append(0)


    tree=[] ##构造kd树
    tree.append(data)
    before=0
    while len(tree)>before:
        if len(tree[before])<=2*k:
            before += 1
            continue
        tree[before]=sorted(tree[before],key=itemgetter(before%(n-1)+1))
        flag=tree[before][int(len(tree[before])/2)][before%(n-1)+1]
        seg1=[]
        seg2=[]
        for i in range(len(tree[before])): ##由某一维度的中位数划分所有的测试点
            if tree[before][i][before%(n-1)+1]<=flag:
                seg1.append(tree[before][i])
            else:
                seg2.append(tree[before][i])
        for i in range(number):## 更新测试点的区域号
            if area[i]==before:
                if data2[i][before%(n-1)+1]<=flag:
                    area[i]=len(tree)
                else:
                    area[i]=len(tree)+1

        tree.append(seg1)
        tree.append(seg2)
        before+=1



    for i in range(number):## 进行测试正确率
        label=[]
        if len(tree[area[i]])==0:
            continue
        for vec in tree[area[i]]:
            label.append(vec[0])
        count=label.count(label[0])
        predict=label[0]
        for j in range(1,len(label)):
            count=count if count>label.count(label[j]) else label.count(label[j])
            predict=predict if count>label.count(label[j]) else label[j]
        if data2[i][0]!=predict:
            error+=1

    print(1-error/number)
    return




if __name__ == '__main__':
    data=input_data()
    training(data,20)
